P3327 [SDOI2015]约数个数和

首先有一个公式:

d(ij)=xiyj[(i,j)=1]d(ij)=\sum_{x|i}\sum_{y|j}[(i,j)=1]

感性理解一下,可以看看这位大佬的博客

那么:

i=1nj=1md(ij)\sum_{i=1}^n\sum_{j=1}^md(ij)

i=1nj=1mxiyj[(x,y)=1]\sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}[(x,y)=1]

改为枚举约数,得:

x=1ny=1mnxmy[(x,y)=1]\sum_{x=1}^n\sum_{y=1}^m \lfloor \frac{n}{x} \rfloor \lfloor \frac{m}{y} \rfloor [(x,y)=1]

x=1ny=1mnxmyd(x,y)μ(d)\sum_{x=1}^n\sum_{y=1}^m \lfloor \frac{n}{x} \rfloor \lfloor \frac{m}{y} \rfloor \sum_{d|(x,y)} \mu(d)

d=1min(n,m)μ(d)x=1ndy=1mdndxmdy\sum_{d=1}^{\min(n,m)} \mu(d) \sum_{x=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{y=1}^{\lfloor \frac{m}{d} \rfloor} \lfloor \frac{n}{dx} \rfloor \lfloor \frac{m}{dy} \rfloor

d=1min(n,m)μ(d)x=1ndndxy=1mdmdy\sum_{d=1}^{\min(n,m)} \mu(d) \sum_{x=1}^{\lfloor \frac{n}{d} \rfloor} \lfloor \frac{n}{dx} \rfloor \sum_{y=1}^{\lfloor \frac{m}{d} \rfloor } \lfloor \frac{m}{dy} \rfloor

f(x)=i=1xxif(x)=\sum_{i=1}^x \lfloor \frac{x}{i} \rfloor ,则原式为

d=1min(n,m)μ(d)f(nd)f(md)\sum_{d=1}^{\min(n,m)} \mu(d) f( \lfloor \frac{n}{d} \rfloor ) f( \lfloor \frac{m}{d} \rfloor )

再看看 f(x)f(x) ,其实就是约数个数的前缀和,原因很简单:

f(x)f(x) 表示不大于 xx 的数的倍数不大于 xx 的数的个数。

d(x)d(x) 表示不大于 xx 的数的倍数为 xx 的数的个数。

可以欧拉筛约数个数再前缀和得到,那么此题就解决了。

时间复杂度 Θ(n+tn)\Theta(n+t\sqrt n)

#include <cstdio>
#include <iostream>
using namespace std;

const int MAXN = 50000;
int t , n , m , k , prime[ MAXN + 5 ];
int mu[ MAXN + 5 ] , d[ MAXN + 5 ] , f[ MAXN + 5 ] , pre_mu[ MAXN + 5 ];
bool vis[ MAXN + 5 ];

void sieve( ) {
	mu[ 1 ] = 1 , d[ 1 ] = 1;
	for( int i = 2 ; i <= MAXN ; i ++ ) {
		if( !vis[ i ] ) {
			prime[ ++ k ] = i;
			mu[ i ] = -1;
			d[ i ] = 2;
		}
		for( int j = 1 ; j <= k && 1ll * i * prime[ j ] <= MAXN ; j ++ ) {
			vis[ i * prime[ j ] ] = 1;
			if( i % prime[ j ] == 0 ) {
				d[ i * prime[ j ] ] = 2 * d[ i ] - d[ i / prime[ j ] ];
				break;
			}
			mu[ i * prime[ j ] ] = -mu[ i ];
			d[ i * prime[ j ] ] = d[ i ] * d[ prime[ j ] ];
		}
	}
	for( int i = 1 ; i <= MAXN ; i ++ ) {
		f[ i ] = f[ i - 1 ] + d[ i ];
		pre_mu[ i ] = pre_mu[ i - 1 ] + mu[ i ];
	}
}

long long solve( int n , int m ) {
	int d = min( n , m );
	long long Ans = 0;
	for( int l = 1 , r ; l <= d ; l = r + 1 ) {
		r = min( n / ( n / l ) , m / ( m / l ) );
		Ans += 1ll * ( pre_mu[ r ] - pre_mu[ l - 1 ] ) * f[ n / l ] * f[ m / l ];
	}
	return Ans;
}
int main( ) {
	sieve( );
	scanf("%d",&t);
	while( t -- ) {
		scanf("%d %d",&n,&m);
		printf("%lld\n", solve( n , m ) );
	}
	return 0;
}